package top.humbleyuan.others;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 20:40
 * @Des 乘积最大子数组
 * @pro 待补充dp方法
 */
public class LeetCode_152 {
    public static void main(String[] args) {
        /**
         * 可以以0为界分成多个子数组，求子数组的最大乘积并取最大值
         * 子数组中最大乘积是从前往后和从后往前都要比一遍
         */

        // 用curSum存当前所有数乘积, sum是最大乘积
        int sum = Integer.MIN_VALUE;
        int curSum = 1;
        int[] nums = {-2, 0, -1};
        for (int num : nums) {
            curSum *= num;
            if(curSum > sum) {
                sum = curSum;
            }

            // 当遇到0断开,curSum变成0
            if(num == 0) {
                curSum = 1;
            }
        }

        curSum = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            curSum *= nums[i];
            if(curSum > sum) {
                sum = curSum;
            }

            // 当遇到0断开,curSum变成0
            if(nums[i] == 0) {
                curSum = 1;
            }
        }

        System.out.println(sum);
    }
}
